package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-18 10:24
 * @description: Functions of this class is 找出一组数中重复的数字
 **/
public class 重复的数字 {
    public static void main(String[] args) {
        int nums[] = {1, 3, 2, 4, 5,3};
        System.out.println("重复的数字为：");
//        search_set(nums);
//        search_or(nums);
//        search_map(nums);
        search_circle(nums);
    }

    /**
     * @param nums 存在重复数字的数组
     *             缺点：元素中不能有0，否则的话，一旦遇到0就会开始自己无限成环
     *             通过找到一个循环的环来找到重复的元素,
     *             可以理解为：因为元素中有重复的，所以一定存在一个环，即先走的fast指针在遇到重复元素时，会重走之前走过的路，即一定会和slow相遇
     */
    private static void search_circle(int nums[]) {
        if (nums != null) {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while (slow != fast) {
                fast = nums[nums[fast]];//fast指针走两步
                slow = nums[slow];//slow指针走一步
            }
            //说明slow==fast了
            //然后清空fast指针，再次进入循环
            fast = 0;
            while (slow != fast) {
                fast = nums[fast];
                slow = nums[slow];
            }
            System.out.println(slow);
        }
    }

    /**
     * @param nums 存在重复数字的数组
     *             缺点：数组中最大的数字不能够超过数组的长度，同时也不能为负数，不然的话容易越界
     *             特殊之处就在于，前面访问过的数组，即索引号较小的数字一旦访问过了，后面如果再出现相同小的索引号的数字，会往回遍历，所以能够找到
     */
    private static void search_map(int nums[]) {
        if (nums != null) {
            int index = 0;
            while (true) {
                //在死循环中寻找
                nums[index] *= -1;//说明该数字已经遍历过了，1 -> -1
                index = nums[index] * -1;//然后继续往下找
                if (nums[index] < 0) {
                    System.out.print(index + " ");
                    break;
                }
            }
        }
    }

    /**
     * @param nums 存在重复数字的数组
     *             缺点；虽然不用开辟额外内存空间，但是数组中数字不能为0，
     *             具体操作就是先和数组中全部元素异或一遍，然后在和从1-数组中最大数字的连续数再异或一遍得到答案
     */
    private static void search_or(int nums[]) {
        int ans = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];//找出数组中最大数字
            }
            ans ^= nums[i];
        }
        for (int i = 1; i <= max; i++) {//然后从1-最大数字，一一相异或
            ans ^= i;
        }
        System.out.println(ans);
    }

}